package com.cat.binaryTree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-fuel-cost-to-report-to-the-capital/
 * @create 2025/9/29 11:26
 * @since JDK17
 */

public class Solution84 {
    List<Integer>[] g;
    long[] cost;
    int[] size;
    int seats;
    void dfs(int cur, int f) {
        if (g[cur].isEmpty()) { // 叶子结点
            return;
        }
        size[cur] = 1;
        for (var u : g[cur]) {  // 子节点
            if (f != u) {   // 没有走来时的路
                dfs(u, cur);    //
                cost[cur] += cost[u] + (size[u] + seats - 1) / seats;   //
                size[cur] += size[u];
            }
        }
    }

    public long minimumFuelCost(int[][] roads, int seats) {
        int n = roads.length;
        this.seats = seats;
        g = new List[n];
        Arrays.setAll(g, i -> new ArrayList<>());
        cost = new long[n];
        size = new int[n];
        for (var road : roads) {
            g[road[0]].add(road[1]);
            g[road[1]].add(road[0]);
        }
        dfs(0, -1);
        return cost[0];
    }
}
